package algorithm.Linked;


import algorithm.Node;

import java.util.Stack;

/**
 * 链表相加
 * 9->3->1            931
 *
 */
public class LinkedAdd {
    public Node addLists1(Node head1, Node head2) {
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        Node cur1 = head1;
        Node cur2 = head2;
        while (cur1 != null) {
            stack1.push(cur1);
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            stack2.push(cur2);
            cur2 = cur2.next;
        }

        Node pre = null;
        Node node = null;
        int ca = 0, n1, n2, sum;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            n1 = stack1.isEmpty() ? 0 : stack1.pop().val;
            n2 = stack2.isEmpty() ? 0 : stack2.pop().val;
            sum = ca + n1 + n2;
            ca = sum / 10;
            pre = node;
            node = new Node(sum % 10);
            node.next = pre;
        }

        if (ca == 1) {
            pre = node;
            node = new Node(ca);
            node.next = pre;
        }
        return node;
    }
}
